#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
    
class Solution1 {
    public:
        string multiply(string num1, string num2) {
            int size1 = num1.size(), size2 = num2.size();
			string str2;
            reverse(num1.begin(), num1.end());
            reverse(num2.begin(), num2.end());
            vector<char> ans(size1+size2, '0');
            for (int i = 0; i < num2.size(); i++) {
                int b = num2[i] - '0';
                int carry = 0;
                int j;
                for (j = 0; j < num1.size(); j++) {
                    int a = num1[j] - '0';
                    int result = a*b + carry;
                    int sum = ans[i+j] - '0';
                    sum += result;
                    if (sum > 9) {carry = sum/10; sum -= carry * 10;}
                    else carry = 0;
                    ans[i+j] = sum + '0';
                }
		if (carry != 0)
		    ans[i+j] = carry + '0';
            }
            bool start = false;
            for (int i = ans.size()-1; i >= 0; i--) {
                if (!start && ans[i] != '0') {start = true; str2 += ans[i];}
                else if (start ) str2 += ans[i];
            }
         return str2.size() == 0 ? "0" : str2;
        }
};

//optimize
class Solution {
    public:
        string multiply(string num1, string num2) {
            int size1 = num1.size(), size2 = num2.size();
            string str2;
            vector<int> ans(size1+size2, 0);
            for (int i = 0; i < num2.size(); i++) {
                int b = num2[size2-i-1] - '0';
                int carry = 0;
                for (int j = 0; j < num1.size(); j++) {
                    int a = num1[size1-j-1] - '0';
                    carry  = a*b + carry + ans[i+j];
                    ans[i+j] = carry%10;
                    carry = carry/10;
                }
	        ans[i+size1] = carry;
            }
            int i = size1+size2-1;
            while(i >0 && ans[i] == 0) i--;
            while(i >= 0) str2 += char(ans[i--]+'0');
            return str2;
        }
};

//N queens

void dfsQueen(int index, int n, vector<int> &colHash, vector<int> &diagHash, vector<int> &diagHash2, vector<string> cur, vector<vector<string> > &ans)
{
    if (index == n) {
	ans.push_back(cur);
	return;
    }

    for (int i = 0; i < n; i++) {
	if (colHash[i] || diagHash[index+i] || diagHash2[index-i + n-1]) continue;
	colHash[i] = 1;
	diagHash[index+i] = 1;
	diagHash2[index-i + n-1] = 1;
	cur[index][i] = 'Q';
	dfsQueen(index+1, n, colHash, diagHash, diagHash2, cur, ans);
	cur[index][i] = '.';
	colHash[i] = 0;
	diagHash[index+i] = 0;
	diagHash2[index-i + n-1] = 0;

    }
}

    vector<vector<string> > solveNQueens(int n) {
	vector<int> colHash(n, 0);
	vector<int> diagHash(2*n-1, 0);
	vector<int> diagHash2(2*n-1, 0);
	vector<vector<string> > ans;
	vector<string> cur(n, string(n, '.')); 
	dfsQueen(0, n, colHash, diagHash, diagHash2, cur, ans);
	return ans;
    }


//test in 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    string result;

    cout << "-----------------Test 1--------------------" << endl;
    result = mySolution.multiply("99","99");
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
